#include <vector>
#include <iostream>

using namespace std;

// the puzzle class
class AI_Puzzle
{
public:
	AI_Puzzle() { ; };
	AI_Puzzle(const vector<int>& init_state) {
		m_init_state.assign(init_state.begin(), init_state.end());
	};
	~AI_Puzzle() { ; };

public:
	// set the init state
	void setInitState(const vector<int>& init_state) {
		m_init_state.assign(init_state.begin(), init_state.end());
	};

	// return true if the problem has solution
	// return false if the problem does not have solution
	// results:  the output sequences of states
	// 
	// We want the final state is
	//
	//		1	2	3
	//		4	5	6
	//		7	8	0
	//
	bool solution(vector<vector<int>>& results)
	{
		// TODO: please fill in the code
		//
		// Yangang Wang, 2020/10/30, @SEU
		//
	}

	// TODO: add more functions below for your own
	//
	// Yangang Wang, 2020/10/30, @SEU
	//

private:
	vector<int> m_init_state;
};

// test function for 8-puzzle problem
void test(const vector<int>& init_state)
{
	AI_Puzzle puzzle;
	vector<vector<int>> results;
	puzzle.setInitState(init_state);
	if (puzzle.solution(results)) {
		printf("solution for the initial state: ");
		for (int i = 0; i < init_state.size(); i++) printf("%d ", init_state[i]);
		printf("\n");
		for (int idx = 0; idx < results.size(); idx++) {
			printf("step %d: ", idx);
			for (int i = 0; i < results[idx].size(); i++) printf("%d ", results[idx][i]);
			printf("\n");
		}
	}
	else {
		printf("no solution for the initial state: ");
		for (int i = 0; i < init_state.size(); i++) printf("%d ", init_state[i]);
		printf("\n");
	}
	printf("\n");
}

void main(int argc, char** argv)
{
	// This is the code for testing the 8-puzzle problem in
	//
	//  'The first project homework for Artifical Intelligence'
	// 
	// Please fill in the code of class 'AI_Puzzle'
	// and write your design, running tests, analysis and etc. into your report
	// Becareful: in each step, we can ONLY exchange with ONE neighbor of digit 0, horizontally or vertically
	//
	// Good Luck!
	//
	// Yangang Wang, 2020/10/30, @SEU

	// Test 1
	//
	//	5   1   2
	//	6   3   0
	//	4   7   8
	vector<int> init_state_1 = { 5, 1, 2, 6, 3, 0, 4, 7, 8 };
	test(init_state_1);

	// Test 2
	//
	//	2   8   3
	//	1   6   4
	//	7   5   0
	vector<int> init_state_2 = { 2, 8, 3, 1, 6, 4, 7, 5, 0 };
	test(init_state_2);

	// Test 3
	//
	//	1   0   2
	//	3   4   5
	//	6   7   8
	vector<int> init_state_3 = { 1, 0, 2, 3, 4, 5, 6, 7, 8 };
	test(init_state_3);

	// Test 4
	//
	//	4   3   5
	//	6   0   8
	//	2   1   7
	vector<int> init_state_4 = { 4, 3, 5, 6, 0, 8, 2, 1, 7 };
	test(init_state_4);

	// Test 5
	//
	//	1   7   3
	//	0   5   4
	//	6   2   8
	vector<int> init_state_5 = { 1, 7, 3, 0, 5, 4, 6, 2, 8 };
	test(init_state_5);
}